ACM里的期望和概率问题 从入门到精通

起因：在2020年一场HDU多校赛上。有这么一题没做出来。

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6829

题目大意：有三个人，他们分别有X，Y，Z块钱（11的期望，0——>1的期望，1——>2的期望，1——>2的期望，.。。。18——>19的期望，18——>19的期望，19——>20的期望。则期望总和是一个账号0——>19的期望加上一个账号0——>20的期望。时间复杂度是O（n）。

C：ZOJ 3415 难度：入门

题目大意：每次由1/m的概率回一滴血，否则扣一滴血，共n滴血，问期望上几轮会死。

题目分析：列出状态转移方程，我们发现是等比数列求和问题，不过当m等于2的时候公比是1，要分开来考虑。另外，需要写一个快速幂。

D：Light OJ 1408 难度 偏难（推荐，经典模型）

题目大意：

求投丢的概率为p;那么如果一直投到连续中k1个,或者连续丢k2个,所需要的球的期望;给出p,k1,k2;

题目分析：

千万不要纠结于已经投了多少次之类云云，写了一个到无限的求和，或者什么第几次出局的方程。想想你就知道，这很难做。我们可以用A[i]表示已经投丢了i个，还要丢多少球出局的期望。B[i]表示已经连续投中了i个，还需要投中几个出局的期望。初始状态当然是A[k1]=B[k2]=0。我们写出来以后会发现，这并不好DP。那高斯消元呢？会TLE，不过好在我们发现这个式子可以用数学直接化简。从而解决了这道题目。总结一下，这道题目难点是状态的描述，不能纠结于一些无价值的参量，比如次数，一个好的状态描述等于成功的一半，这非常的DP了。

E Light OJ 1342 难度 偏难

题目大意：

现在有n个物品，他们编号是1-n，每个物品都有一个自己的重量Wi。物品分两类，第一类物品，拿了以后不会放回去。第二类，拿了还会放回去， 每一次随机等概率拿。问使得所有物品都被拿过时拿过的物品的总重量的期望。

题目分析：

老样子，先描述好状态很轻松得到一个方程。这道题目有价值的参量显然是，还剩下的物品总数，第一类物品数量，第二类物品数量，不过它们有一个和的关系，两个就够了。我们这里选择用dp[n][m]表示当前剩下n个一类物品，m个二类物品的期望。那下一次无非是拿一类或二类，问题是重量怎么处理呢？我们很容易发现，对于第二类物品，拿了就会拿出去，又是等概率拿，所以每次拿出的二类物品的期望重量时确定的，即二类物品重量平均值。而一类物品呢？拿了就放不回去，最后每个都拿了且只拿了一次，所以结果加上一类物品的总和就行了。初状态是dp[0][j]和dp[0][i]，分别用一个一维的DP预处理一下，再总体DP一下。复杂度是O（n^2）

不过如果你读过我上面提到的三个大佬的论文，并且看过论文题目，你一定知道，一个n面骰子（假设严格随机等概率投），使得所有面都朝上过的次数的期望是1/1+1/2+1/3+1/4...+1/n，也就是调和级数。我们不难发现二类物品就是这个模型，而一类物品对结果的影响就是加上一类物品总重，所以我们可以很轻松的用O（n）的复杂度解决这个问题。

F HDU 6052 难度 难

题目大意：

有一个n*m的矩阵（1[0,b−1]的骰子,各投d次得到一d位b进制数，最后数字大的赢。一：轮流投,二：第一个人投d次之后,第二个人投。两人都采用最佳策略，问两种情况下第一个人的胜率。0d,b题目分析：

首先是如何描述状态，很容易想到用dp[i][j][k]表示第一个数是i，第二个数是j的情况下，当前是第k个人填数的情况下。第一个人的胜率，然后模拟填写过程。不过我们知道dp[i][j]的转移方程是求max或者min得到的，不可倒推。因此只能用dfs来写。紧接着的问题是，我们没法用当前值标记某个位填了0。因此我们做一个变换，改填0-b-1为1-b。考虑到比较值的大小是从高位到低位比较大小。这个变换是等价的。从而使得i，j能表示某个位有没有填数，从而使得第三维k可以消掉。（b+1)^dQ HDU 5819 难度 普通

题目大意：

数轴上一段0-n+1上有n个棋子分别在1，2，3.。。n上。每个棋子要么往左，要么往右，单位时间走单位距离，到头尽头会回头。两个棋子相遇后会战斗，1/2的概率胜利，胜利的那个接着走，失败的就消失。问第n个棋子活到最后的概率。

题目分析：

一开始看成了每个棋子的胜率，首先发现了同向的棋子之间比较好处理，然后发现了步数有限，而且决斗顺序有一定规律，一个棋子往右，那它左边的情况比较好处理，右边就开始抓瞎了，然后再读了一遍题目，哦。读错题目了，嘿嘿嘿。

只要知道第n个棋子左边多少棋子自左往右就行了。dp[i][j]表示前i个棋子j个往右的概率。如果这个棋子往右，那前i-1个棋子在这个棋子被n干掉前没有机会干掉n。如果这个棋子往左去找n干架了，那它一定干翻了1-i-1。后者是对dp[i-1][j]/(2^j)求和。很容易想到优化。

时间复杂度O（n^2）

R  HDU 4089 难度 偏难

题目大意：

n个人在排队，每次，队首都会有如下4种情况：p1概率无事发生，p2概率跑到队列最后，p3概率离开队列，p4概率停止一切操作。问停止一切操作后，原来的第m号人在队列中顺序小于等于k的概率。

(1 题目分析：

很容易描述状态dp[i][j]为共j个人，原来的第m号人在队列第i个（i